Lambda the Ultimate

Event-Based Programming without Inversion of Control. Philipp Haller and Martin Odersky.

Scala is different from other concurrent languages in that it contains no language support for concurrency beyond the standard thread model offered by the host environment. Instead of specialized language constructs we rely on Scala's general abstraction capabilities to define higher-level concurrency models. In such a way, we were able to define all essential operations of Erlang's actor-based process model in the Scala library.

However, since Scala is implemented on the Java VM, we inherited some of the deficiencies of the host environment when it comes to concurrency, namely low maximum number of threads and high context-switch overhead. In this paper we have shown how to turn this weakness into a strength. By defining a new event-based model for actors, we could increase dramatically their efficiency and scalability. At the same time, we kept to a large extent the programming model of thread-based actors, which would not have been possible if we had switched to a traditional event-based architecture, because the latter causes an inversion of control.

(There's not really a proper abstract. The above is from the conclusion.)

I enjoyed this paper. It's a quick read and a nice demonstration of some of Scala's cool features. It's also a good example of using exceptions as delimited control operators, and in fact the one substantial restriction is imposed by the lack of the more powerful operators. They use Scala's type system to reduce the burden of this restriction, however, since they're able to state that a particular statement never returns normally (and thus must not be followed by more statements).

Those interested in the language/library boundary will also find it interesting for this reason:

The techniques presented in this paper are a good showcase of the increased flexibility offered by library-based designs. It allowed us to quickly address problems with the previous thread-based actor model by developing a parallel class hierarchy for event-based actors. Today, the two approaches exist side by side. Thread-based actors are still useful since they allow returning from a receive operation. Event-based actors are more restrictive in the programming style they allow, but they are also more efficient.

They have some fairly impressive empirical scalability results as well.

Socially Responsive, Environmentally Friendly Logic
by Samson Abramsky

We consider the following questions: What kind of logic has a natural semantics in
multi-player (rather than 2-player) games? How can we express branching quantifiers, and
other partial-information constructs, with a properly compositional syntax and semantics?
We develop a logic in answer to these questions, with a formal semantics based on multiple
concurrent strategies, formalized as closure operators on Kahn-Plotkin concrete domains.
Partial information constraints are represented as co-closure operators. We address the
syntactic issues by treating syntactic constituents, including quantifiers, as arrows in a
category, with arities and co-arities. This enables a fully compositional account of a wide
range of features in a multi-agent, concurrent setting, including IF-style quantifiers.

This paper seems to unify multiple interesting directions - logic, game semantics, concurrent constraint programming (and concurrent programming in general).

At the same time it remains very accessible, without overwhelming amount of math, so can be hopefully useful not only for academics. I, for one, was waiting for exactly this kind of paper for two years (and my interest is very practical).

Multiplayer Curry-Howard correspondence, anyone? Or Curry-Howard for web services?

Abstracting Allocation: The New new Thing. Nick Benton.

We introduce a Floyd-Hoare-style framework for specification and verification of machine code programs, based on relational parametricity (rather than unary predicates) and using both step-indexing and a novel form of separation structure. This yields compositional, descriptive and extensional reasoning principles for many features of low-level sequential computation: independence, ownership transfer, unstructured control flow, first-class code pointers and address arithmetic. We demonstrate how to specify and verify the implementation of a simple memory manager and, independently, its clients in this style. The work has been fully machine-checked within the Coq proof assistant.

This is, of course, related to TAL, PCC etc. If you find the deatils too much, I suggest reading the discussion (section 7) to get a feel for the possible advantages of this approach.

There've been a couple of threads recently about safety-critical code (Rules for, and in real-time Java). Safety-critical code necessarily includes careful handling of failure situations. Or does it? Here's another take on failure handling, from the opposite direction:

Enhancing Server Availability and Security Through Failure-Oblivious Computing (Rinard et al., 2004) was originally presented at OSDI '04, but hasn't previously been featured here:

We present a new technique, failure-oblivious computing, that enables servers to execute through memory errors without memory corruption. Our safe compiler for C inserts checks that dynamically detect invalid memory accesses. Instead of terminating or throwing an exception, the generated code simply discards invalid writes and manufactures values to return for invalid reads, enabling the server to continue its normal execution path.

We have applied failure-oblivious computing to a set of widely-used servers from the Linux-based open-source computing environment. Our results show that our techniques 1) make these servers invulnerable to known security attacks that exploit memory errors, and 2) enable the servers to continue to operate successfully to service legitimate requests and satisfy the needs of their users even after attacks trigger their memory errors.

The paper includes descriptions of how this technique was applied with good results to servers such as Apache and Sendmail, as well as to client programs such as Pine, Mutt, and Midnight Commander.

The paper also raises concerns about the potential for such techniques to create a bystander effect (although the term moral hazard might be more appropriate here), influencing programmers to be less careful about error handling because they have a safety net.

This work was performed on programs written in C, and there's a temptation to think that the approach is only applicable to memory-unsafe languages. However, there's a connection here to the approach used by some of the classic shell scripting languages and their descendants such as Perl, in which certain kinds of failure are silently tolerated in the interests of keeping the program running. The approach could also have potential applications in other memory-safe languages, providing the potential for higher-availability programs, as noted in the paper's conclusion.

While most language implementors aren't going to rush to incorporate failure-oblivious approaches in their languages, the positive results obtained from this work are thought-provoking, and could inspire other less traditional but effective ways of handling failure.

CLPython is an implementation of the Python programming language in Common Lisp. It is developed by Willem Broekema with support from Franz Inc. CLPython is released under the LLGPL.

You might enjoy browsing the source code.

Programming Languages and Lambda Calculi looks like a comprehensive treatement of the semantics of typed and untyped call-by-value programming languages. I imagine if one had a basic undergraduate education in programming language theory and wanted to get up to speeed in a hurry this would be a great resource.

Registration is now open for the 9th Annual ICFP Programming Contest. The ICFP contest is an event that traditionally raises interest in the LtU community.

A more detailed announcement found in the forum mentions that this year's theme is "computational archaeolinguistics." Intriguing.

Pluvo is a functional and imperative programming language intended to be highly practical for scripting and CGIs, interpreted using a just-in-time compiler. Its hybrid dynamic and strict typing is flexible enough to allow duck typing. Its functions are, more specifically, closures, and it allows object orientation using prototypes.

From Sean B. Palmer.

Knowing he's a big fan of Python I expected a fair bit of influence - and there is, in fact the implementation is written in Python. Flexibility over typing was to be expected too, Sean's done a lot of work around RDF. Slightly surprising was Pluvo's syntax, which owes more to Bash.

The first 10 Prolog Programming Contests took place in Ithaca (1994), Portland (1995), Bonn (1996), Leuven (1997), Manchester (1998), Las Cruces (1999), Paphos (2001), Copenhagen (2002), Mumbay (2003) and Saint-Malo (2004). The contest organisers have written this book, containing the (slightly reworked) questions and an answer (in Prolog of course) for each question... The book is now also freely downloadable on this page.

For your enjoyment...

Though his contributions to computer science predate our current notion of a computer by nearly three hundred years, some claim Leibniz to have been the first computer scientist and information theorist. A history department on Ltu should in my opinion pay homage to such a character of fame, hence a link to a beautiful site dedicated to Gottfried Wilhelm Leibniz